package OptimalAlgorithm.DivideAndConquer_Quicksort;

import java.util.Random;

//https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
public class FindKthLargest {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length - 1,k);
    }

    private int qsort(int[] nums, int l, int r,int k) {
        Random random = new Random();
        int key = nums[random.nextInt(nums.length) % (r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        while (i <= right - 1){

            if(nums[i] == key){
                i++;
            }else if(nums[i] < key){
                swap(left + 1,i,nums);
                i++;
                left++;
            }else {
                swap(right - 1,i,nums);
                right--;
            }
        }
        if(r - right + 1 >= k){
            return qsort(nums,right,r,k);
        }else if(r - left >= k){
            return key;
        }else {
            return qsort(nums,l,left,k - (r - left));
        }
    }

    private void swap(int i,int j,int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
